//
// Created by francklinson on 2021/5/18.
//
#include <string>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> fre;
        // 统计字符出现的数量
        for (auto &x:s)++fre[x];
        // 放入vector
        vector<pair<char, int>> v;
        v.reserve(fre.size());
        for (auto &x:fre) {
            v.emplace_back(x);
        }
        // 自定义排序函数
        sort(v.begin(), v.end(), [](pair<char, int> &a, pair<char, int> &b) {
            return a.second > b.second;
        });
        string ans;
        for (auto &x:v) {
            for (int i = 0; i < x.second; ++i) {
                ans.push_back(x.first);
            }
        }
        return ans;

    }
};

int main() {
    Solution sol;
    cout << sol.frequencySort("tree") << endl;
    cout << sol.frequencySort("cccaaaa") << endl;
    cout << sol.frequencySort("Aabb") << endl;
    return 0;
}